package com.leetcode.dfs;

import java.util.Arrays;

public class JumpGame {

    public static void main(String[] args) {
        int[] arr = {2, 3, 1, 1, 4};

    }

    private int res = 10000;

    public void jump(int[] nums) {
        dfs(nums, 0, 0);
    }

    private void dfs(int[] nums, int ind, int tmpRes) {
        if (ind == nums.length - 1) {
            res = Math.min(res, tmpRes);
            return;
        }
        if (ind > nums.length - 1) {
            return;
        }
        for (int i = 1; i <= nums[ind]; i++) {
            tmpRes++;
            dfs(nums, ind + i, tmpRes);
            tmpRes--;
        }
    }

    private int dp(int[] nums) {
        int[] res = new int[nums.length];
        Arrays.fill(res, 10000);
        res[0] = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = 1; j <= nums[i] && i + j < nums.length; j++) {
                res[i + j] = Math.min(res[i] + 1, res[i+j]);
            }
        }
        return res[res.length - 1];
    }
}
